/*
 * =====================================================================================
 *
 *       Filename:  suffixarray.c
 *
 *    Description:  后缀数组倍增算法实现
 *
 *        Version:  1.0
 *        Created:  2012年07月02日 17时13分52秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Regan (), lcqhigh@gmail.com
 *        Company:
 *
 * =====================================================================================
 */
#include	<stdio.h>
#include	<string.h>
#include	<stdlib.h>


#define	MAX_STR_LEN 1023			/*  */
//the string length must not be greater than 1024
int radix_suffix_sort(int *sa, int *rank, int step, int start, int len)
{
    short count[MAX_STR_LEN+1] = {0x00};
    int   ta[MAX_STR_LEN+1] = {0x00};
    int   randbak[MAX_STR_LEN+1];
    int k = 0, checkidx, rankno;
    sa += start;
    int res = 0;
    //radix sort by the step-stage result
    for (k = 0; k < len; ++k) {
        checkidx = sa[k] + step;
        ++count[rank[checkidx]];
    }

    for (k = 1; k < 1024; ++k)
        count[k] += count[k-1];

    for (k = len-1; k >= 0; --k) {
        checkidx = sa[k] + step;
        rankno = rank[checkidx];
        ta[count[rankno]-1] = sa[k];
        --count[rankno];
    }

    for (k = 0; k < len; ++k)
        sa[k] = ta[k];

    //update the rank array
    int startRank = rank[sa[0]];
    randbak[sa[0]] = startRank;
    for (k = 1; k < len; ++k)
    {
        if (rank[sa[k]+step] == rank[sa[k-1]+step])
        {
            ++res;
            randbak[sa[k]] = randbak[sa[k-1]];
        }
        else 
            randbak[sa[k]] = startRank + k;
    }
    for (k = 1; k < len; ++k)
        rank[sa[k]] = randbak[sa[k]];

    return res;
}

void debug_info(int step, const char* str, int idxArr[], int rankarr[], int n)
{
    printf ( ">>>>after the %d loop the sorted string<<<\n", step);
    int k = 0;
    for (k = 0; k < n; ++k)
        printf ( "%s\t%d\n", str+idxArr[k], rankarr[idxArr[k]]);
    printf ( "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n" );
}

int create_suffix_array(const char *str)
{
    int rank[MAX_STR_LEN+1] = {0x00};
    int SA[MAX_STR_LEN+1];
    short count[128] = {0x00};
    int n = strlen(str) + 1;
    int k, previdx, curridx;
    //radix sort by the first character
    for (k = 0; k < n; ++k)
        ++count[(int)str[k]];
    for (k = 1; k < 128; ++k)
        count[k] += count[k-1];
    for (k = n-1; k >= 0; --k) {
        SA[count[(int)str[k]]-1] = k;
        --count[(int)str[k]];
    }
    //construct the rand array, 使用并列排名
    rank[SA[0]] = 0;
    for (k = 1; k < n; ++k)
    {
        curridx = SA[k];
        previdx = SA[k-1];
        if (str[curridx] == str[previdx])
            rank[curridx] = rank[previdx];
        else
            rank[curridx] = k;
    }
    debug_info(1, str, SA, rank, n);
    //倍增排序
    int depth = 2;
    int length, begin, over = 0;
    for (; depth <= n && !over; depth *= 2)
    {
        over = 1;
        for (k = 1; k < n; ++k)
        {
            length = 1;
            begin = k - 1;
            while (rank[SA[k]] == rank[SA[k-1]] && k < n)
            {
                ++length;
                ++k;
            }
            if (length > 1)
            {
                over = 0;
                radix_suffix_sort(SA, rank, depth/2, begin, length);
            }
        }
        if (!over)
            debug_info(depth, str, SA, rank, n);
    }
    return 0;
}

int main(int argc, char *argv[])
{
    char str[1000];
    while (scanf("%s", str) != EOF) 
    {
        create_suffix_array(str);
    }
    return 0;
}
